package 回溯;

public class leetcode39And40DP {
	/**
	 *为啥 要 写 递归 因为 递归 更符合             人的 自然 智慧
	 *你不可能 直接 憋 状态 转移 方程吧 
	 *动态规划 比对应 着 一个 递归 
	 *这是左程云的 原话对吧  
	 * 
	 * 
	 * 动态 规划 研究的  是 结果 
	 * 回溯  结果 和 过程 都可以 研究 但就是   效率低 对吧
	 * 
	 * 
	 * 这里 研究 的 是 39  和 40  两道题 满足 要求 的     结果的  的个数 
	 */
	//39  可以 重复 选择 自己
/**
 * 下面这个 递归 肯定 是 有重复 过程的 
 * 没有 重复 过程的 递归 是 没办法 优化的 
 */
	public  static int process(int nums[],int rest,int index) {
		if(rest == 0) {
//			 这说明 找到 一种结果 
			return 1;
		}
		int ways = 0;
		for(int i = index ;i < nums.length && rest-nums[i] >= 0; i++) {
			
			ways += process(nums,rest - nums[i],i);
		}
		return ways;
	}
	
	
	
	public static int process(int nums[],int rest,int index,int dp[][]) {
			if(dp[index][rest] !=-1) {
				return dp[index][rest];
			}
			if(rest == 0) {
				dp[index][rest] = 1;
				return dp[index][rest];
			}
			int ways = 0;
											   // 过滤 条件 这里 不写 basecase 下面 就要写  要不然 就会 越界 对吧
			for(int i = index;i <nums.length  && rest - nums[i]>=0;i++) {
				ways += process(nums,rest-nums[i],i,dp);
			}
//			  下面的 两行代码 可以  直接 合并 成 一行代码 
//			dp[index][rest] = ways;
			return dp[index][rest] = ways;
	}
	
	public static int solution(int nums[],int target) {
		int len  = nums.length;
		int dp[][] = new int [len][target+1];
		for(int i = 0;i < len;i++) {
			for(int j = 0;j <= target;j++) {
//				if(j==0) {
//					dp[i][j] = 1;
//				}
//				else
					dp[i][j] = -1;
			}
		}
//		  其实这里 没有 必要 初始化 为 -1 吧 个人 感觉  对于 这道题  而言 
		process(nums,target,0,dp);
		     for(int [] i :dp ) {
		    	 for(int j : i) {
		    		 System.out.print(j+" ");
		    	 }
		    	 System.out.println();
		     }
//		       return        process(nums,target,0,dp);
		     return dp[0][target];
	}
/**
 * 动态 规划 版本
 * 主要的 是理解 什么 啊  
 * 1：这个 缓存表的  下标 表示的  是什么 意思
 * 2： 缓存 表中 存的 值 表示的 是什么 意思 
 * 这道题 而言：
 * index rest  dp[index][rest]是二维 缓存 表的 下标   和 值  表示的 含义 为 到 index 位置 时 剩余 rest 时候 有多少种 结果 数 
 * 
 * @param args
 */
	public static int dp(int nums[],int target) { 
		int len = nums.length;
		int dp [][]= new int [len][target+1];
//		 dp表 初始化 还是 要有的  当  rest == 0 结果 为  1 
//		for(int index = 0;index < len;index++) {
//			dp[index][0] = 1;
//			int ways = 0;
//			for(int i = 1; rest <= target && rest - nums[index] >= 0; rest++) {
//				ways += dp[index][rest - nums[index]];
//			}
//			dp[index][rest] = ways;
//		}
//		  你注意 这是 个  二维表  填表 时 肯定  是 需要 两个 for 循环的  
		for(int rest = 0; rest <= target;rest++) {
/**
 * 注意填表的 顺序  下面的 这种写法 是 不正确的 吧
 * 目前 还没有测试 
 * 不过 从 填表的 顺序 来看的 话 下面的 顺序 确实 是错  的 
 * int index = 0; index < len      index++ 
 */
			for(int index = len-1;index >= 0; index--) {
				if(rest == 0) {
					dp[index][rest] = 1;
					/**
					 * 这直接 和 递归的 过程 完全 是 一样的 离谱 不 
					 * 完全一样 我靠 
					 * 这里的 continue  就是 相当于 原递归 中的 return
					 */
					continue;
				}
				int ways = 0;
				for(int i = index; i <nums.length && rest - nums[i] >=0;i++ ) {
					ways += dp[i][rest - nums[i]];
				}
				dp[index][rest] = ways;
			}
		}
		for(int i[] : dp) {
			for(int value : i) {
				System.out.print(value +" ");
			}
			System.out.println();
		}
		return dp[0][target];
	}
	/**
	 * 换一种 填表的 顺序   注意 下面 这种 方法 和 dp 方法中 填表的区别
	 * 其实没有 区别 
	 */
	public static int dp1(int nums[],int target) {
		int len =nums.length;
		int dp [][] = new int [len][target+1];
		for(int index = len - 1; index >= 0; index--) {
			dp[index][0] = 1;
			for(int rest = 1; rest <= target;rest++) {
				
				int ways = 0;
				for(int i = index ;i < len && rest - nums[i] >=0;i++) {
					ways += dp[i][rest - nums[i]];
				}
				dp[index][rest] = ways;
			}
		}
		for(int i [] : dp) {
			for(int value : i) {
				System.out.print(value + " ");
			}
			System.out.println();
		}
		return dp[0][target];
	}
	public static void main(String []args) {
		int candidates []= {2,3,4,5,6};
				int target = 8;
		System.out.println(process(candidates,target,0));
		System.out.println(solution(candidates,target));
		System.out.println(dp(candidates,target));
		System.out.println(dp1(candidates,target));
	}
}
